6 15
0 0 450
0 1 550
1 2 300
1 3 400
2 4 220
2 5 280
3 6 500
3 7 380
4 8 320
4 9 420
5 10 260
5 11 340
0 12 480
1 13 520
2 14 360
5
0 150 1
1 200 2
2 250 3
3 300 4
4 350 5
12
0 0 6 150
1 1 3 200
2 2 5 100
3 4 0 250
4 3 6 180
5 5 1 80
6 7 8 220
7 9 2 280
8 10 13 240
9 11 4 160
10 12 7 300
11 14 9 320